/*
 * @lc app=leetcode.cn id=1640 lang=cpp
 *
 * [1640] 能否连接形成数组
 */

// @lc code=start
class Solution {
public:
    bool canFormArray(vector<int> &arr, vector<vector<int>> &pieces) {
        unordered_map<int, int> idxs;
        int n = pieces.size();
        for (int i = 0; i < n; i++) {
            idxs[pieces[i][0]] = i;
        }
        n = arr.size();
        for (int i = 0; i < n;) {
            if (idxs.find(arr[i]) == idxs.end()) {
                return false;
            }
            int j = idxs[arr[i]], size = pieces[j].size();
            for (int k = 0; k < size; k++) {
                if (arr[i + k] != pieces[j][k]) {
                    return false;
                }
            }
            i += size;
        }

        return true;
    }
};
// @lc code=end
